package Demo30;

import java.util.HashMap;

/**
 * 和为k的子数组
 * https://leetcode.cn/problems/subarray-sum-equals-k/
 * 前缀和+hash表
 * 前缀和是 sum hash表来存放前缀和,和计数前缀和
 * 当我们获取  i 和为k的子数组的时候, 就可以去 hash表里面找有多少个 前缀和是等于 当前i的前缀和 -k 并统计起来
 * 但是我们要考虑一种情况,就是 数组的和为 k 的时候
 * 数组的和 - k == 0  我们要去 [0, -1] 之间找前缀和 是没法找到的, 所有我们先添加 一个 <0,1> 进hash表里面
 */

class Solution {
    public int subarraySum(int[] nums, int k) {
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        hashMap.put(0,1);// 这里加一个 (0,1) 就是防止 数组的和等于 k 的情况

        int ret = 0,sum = 0;// 这里ret 代表返回值,子数组的个数, sum 代表的是前缀和
        for(int i = 0; i < nums.length;i++) {
            sum += nums[i];
            ret += hashMap.getOrDefault(sum - k,0);
            hashMap.put(sum,hashMap.getOrDefault(sum,0) + 1);
        }
        return ret;
    }
}
class Demo {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int ret = solution.subarraySum(new int[] {1,1,1},2);
        System.out.println(ret);
    }
}
